package com.algorithm.cjm.july.chapter1.ch2;


import java.util.Arrays;

/**
 * 字符串的包含
 * 给定一个长字符串a 和短字符串b.判断出短字符串b 中所有字符都在长字符串a 中
 *
 * Created by jieming.chen on 2020/1/11
 */
public class StringContain2 {

    static StringContain2 object = new StringContain2();

    public static void main(String[] args) {
        String a = "bacdefg";
        String b = "w";
        boolean c = object.stringContain(a, b);
        System.out.println(c);

        String a1 = "bacdefg";
        String b1 = "b";
        boolean c1 = object.stringContain(a1, b1);
        System.out.println(c1);
    }

    /**
     * 排序后轮询
     * 1. 给字符串排序；
     * 2. 双指针法，慢指针从短字符串开始遍历，快指针从长字符串开始遍历；
     * 3. 如果快指针，指向的位置小于慢指针，则快指针加一，如果快指针出了边界或者大于慢指针，则 reture false；
     * 4. 快指针和慢指针指向的位置相等，慢指针加一。
     *
     * 两个字符串排序  O(mlogm) + O(nlogn) 次操作
     * 之后的线性扫描需要 m+n
     *
     * @param a
     * @param b
     * @return
     */
    private boolean stringContain(String a, String b) {
        char[] arrA = a.toCharArray();
        char[] arrB = b.toCharArray();
        Arrays.sort(arrA);
        Arrays.sort(arrB);

        for (int pa = 0, pb = 0; pb < arrB.length; ) {
            while (pa < arrA.length && arrB[pb] > arrA[pa]) {
                pa++;
            }
            if (pa >= arrA.length || arrA[pa] > arrB[pb]) {
                return false;
            }
            pb++;
        }
        return true;
    }
}
